package com.ma.huawei.a0420;

/**
 * @ClassName LeetCode494
 * @Author: mayongqiang
 * @DATE 2022/4/23 23:05
 * @Description:
 */

public class LeetCode494 {
    public static void main(String[] args) {
        //nums = [1,1,1,1,1], target = 3  一共有 5 种方法让最终目标和为 3 。
        int[] nums = {1, 1, 1, 1, 1};
        int target = 3;
        System.out.println(findTargetSumWays(nums, target));
    }

    public static int findTargetSumWays(int[] nums, int target) {
        return dfs(0, nums, target);
    }

    static int dfs(int idx, int[] nums, int target) {

        if (idx == nums.length) {
            return target == 0 ? 1 : 0;
        }
        //System.out.println(target);
        return dfs(idx + 1, nums, target - nums[idx])
                + dfs(idx + 1, nums, target + nums[idx]);

    }
}
